package th.retrofit.lib;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/distinct-subsequences/
 * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 *
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
 *
 * 题目数据保证答案符合 32 位带符号整数范围。
 */
public class Solution115 {

    //抽取字符，填入builder，通过回溯实现，超时
    int count = 0;
    public int numDistinct(String s, String t) {
        char[] sArr = s.toCharArray();
        StringBuilder builder = new StringBuilder();
        backtrack(sArr, builder, t, 0);
        return count;
    }

    private void backtrack(char[] sArr, StringBuilder builder, String t, int index) {
        if (builder.length() == t.length() && t.equals(builder.toString())) {
            count++;
            return;
        }
        for (int i = index; builder.length() < t.length() && i < sArr.length; i++) {
            builder.append(sArr[i]);
            backtrack(sArr, builder, t, i + 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }

    //记忆化搜索+递归
    public int numDistinct1(String s, String t){
        int sLen = s.length(), tLen = t.length();
        Integer[][] dp = new Integer[sLen][tLen];
        return dfs(s, t, 0, 0, dp);
    }

    private int dfs(String s, String t, int i, int j, Integer[][] dp) {
        if (j == t.length()) return 1;
        if (t.length() - j > s.length() - i) return 0;
        if (dp[i][j] != null) return dp[i][j];
        if (s.charAt(i) == t.charAt(j)) {
            dp[i][j] = dfs(s, t, i + 1, j + 1, dp) + dfs(s, t, i + 1, j, dp);
        } else {
            dp[i][j] = dfs(s, t, i + 1, j, dp);
        }
        return dp[i][j];
    }

    // 动态规划当s[i] = t[j], 则dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]，否则dp[i][j] = dp[i + 1][j]
    public int numDistinct2(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        int[][] dp = new int[sLen + 1][tLen + 1];
        for (int i = 0; i <= sLen; i++) {
            dp[i][tLen] = 1;
        }
        for (int i = sLen - 1; i >= 0; i--) {
            for (int j = tLen - 1; j >= 0; j--) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution115().numDistinct2("rabbbit", "rabbit"));

    }
}
